#pragma once
#include <algorithm4cpp/dictionary_tree.h>
using namespace algorithm4cpp;

typedef const void * tag;
typedef dictionary_tree<tag> dictionary;

class tag_dictionary_tree_test :
	public Test, public dictionary::tree_listener
{
protected:
	typedef shared_ptr<dictionary>	tree_ptr;
	typedef vector<tree_ptr>	path;
	typedef set<tag>	tag_set;

public:
	tag_dictionary_tree_test(void);
	virtual ~tag_dictionary_tree_test(void);

protected:
	virtual void SetUp()
	{
		head = L'\0';

		keys.push_back( L"abdef" );
		keys.push_back( L"abdefhj" );
		keys.push_back( L"abdefzjlk" );
		keys.push_back( L"abdxf" );
		keys.push_back( L"ybdef" );
		keys.push_back( L"azdef" );

		tree.reset( new dictionary( head ) );
		tree->listener(this);
	}

	virtual void TearDown()
	{

	}

	void test_constructor( wchar_t c )
	{
		dictionary * tree = new dictionary( c );
		EXPECT_EQ( c, tree->head() );
	}

	void test_one_merge( const wstring & x )
	{
		tree->merge( x, &x );
		EXPECT_EQ(head, tree->head() );

		tag_set tags;
		tree->get_all_tags(tags);
		EXPECT_LE( 1, tags.size() );
		EXPECT_TRUE( tags.end() != tags.find(&x) );

		path p;
		const wchar_t * c = x.c_str();
		size_t length = x.length();
		tree->find_path( c, length, p );
		EXPECT_EQ( length, p.size() );
	}
	void test_merge()
	{
		for(size_t index = 0; index < keys.size(); ++index ) {
			test_one_merge( keys[index] );
		}
	}
	void test_one_remove( const wstring & x )
	{
		// pre-remove check
		tag_set tags;
		tree->get_all_tags( tags );
		EXPECT_TRUE( tags.find( &x ) != tags.end() );

		// do remove
		tree->remove( x, &x );
		EXPECT_EQ(head, tree->head() );

		// check again
		tags.clear();
		tree->get_all_tags( tags );
		EXPECT_TRUE( tags.find( &x ) == tags.end() );
	}
	void test_many_remove()
	{
		for ( size_t index = 0; index < keys.size(); ++index ) {
			test_one_merge( keys[index] );
		}

		for ( size_t index = 0; index < keys.size(); ++index ) {
			test_one_remove( keys[index] );
		}

		// check path
		for ( size_t index = 0; index < keys.size(); ++index ) {
			const wchar_t * c = keys[index].c_str();
			size_t length = keys[index].length();
			path p;
			tree->find_path( c, length, p );
			EXPECT_TRUE( p.empty() );
		}

		tag_set tags;
		tree->get_all_tags(tags);
		EXPECT_TRUE( tags.empty() );
	}


	void test_tags()
	{
		wstring x;
		x.resize( keys[0].size(), L'\0' );
		x.assign( keys[0].c_str() );
		assert( x.c_str() != keys[0].c_str() );

		test_tags(x);
		
		for ( size_t index = 0; index < keys.size(); ++index ) {
			test_tags( keys[index] );
		}

		tag_set all_tags;
		tree->get_all_tags(all_tags);
		EXPECT_TRUE( all_tags.find(&x) != all_tags.end() );

		for ( size_t index = 0; index < keys.size(); ++index ) {
			EXPECT_TRUE( all_tags.find(&keys[index]) != all_tags.end() );
		}

		path p;
		tree->find_path( x.c_str(), x.length(), p );

		EXPECT_EQ( x.length(), p.size() );
		if ( p.size() > 0 )	{
			tag_set tags;
			p[p.size()-1]->get_tags(tags);
			EXPECT_EQ(2, tags.size());
		}
	}

	void test_tags( const wstring &x ) 
	{
		test_one_merge( x );

		tag_set all_tags;
		tree->get_all_tags(all_tags);
		EXPECT_TRUE( all_tags.find(&x) != all_tags.end() );

		path p;
		tree->find_path( x.c_str(), x.length(), p );
		EXPECT_EQ(x.length(), p.size());

		if ( p.size() > 0 ) {
			tag_set tags;
			p[p.size()-1]->get_tags(tags);
			EXPECT_TRUE( tags.find(&x) != tags.end() );
		}
	}

	void test_listener()
	{
		for ( size_t index = 0; index < keys.size(); ++index ) {
			wcout << L"merging: " << keys[index] << L", appended tree trace: ";
			appended = false;
			appended_characters.clear();
			test_one_merge( keys[index] );
			EXPECT_TRUE( appended );
			for ( size_t character_index = 0; character_index < appended_characters.size(); ++ character_index ) {
				EXPECT_TRUE( keys[index].find( appended_characters[character_index] ) != string::npos );
			}
			cout << endl;
		}

		for ( size_t index = 0; index < keys.size(); ++index ) {
			wcout << L"removing: " << keys[index] << L", removed tree trace: ";
			removed = false;
			removed_characters.clear();
			bool expected_removed = true;
			
			path p;
			tree->find_path( keys[index].c_str(), keys[index].length(), p );
			if ( p.empty() ) {
				assert( false );
			}

			tag_set tags;
			p[p.size() - 1]->get_all_tags( tags );
			if ( tags.size() > 1 ) {
				expected_removed = false;
			}

			test_one_remove( keys[index] );

			EXPECT_EQ( removed, expected_removed );
			for ( size_t character_index = 0; character_index < removed_characters.size(); ++ character_index ) {
				EXPECT_TRUE( keys[index].find( removed_characters[character_index] ) != string::npos );
			}
			cout << endl;
		}
	}

	void test_find_path()
	{
		for ( size_t index = 0; index < keys.size(); ++index ) {
			test_find_path( keys[index] );
		}
	}

	void test_find_path( const wstring & x )
	{
		tree->merge( x, &x );

		const wchar_t * c = x.c_str();
		size_t length = x.length();
		for ( size_t size = 1; size <= length; ++size ) {
			path p;
			tree->find_path( c, size, p );
			EXPECT_EQ( size, p.size() );
		}
	}
public:
	virtual void on_tree_appended( dictionary * tree )
	{
		appended = true;
		appended_characters.push_back( tree->head() );
		wcout << tree->head();
	}
	virtual void on_tree_removed( dictionary * tree )
	{
		removed = true;
		removed_characters.push_back( tree->head() );
		wcout << tree->head();
	}

protected:
	wchar_t							head;
	shared_ptr<dictionary>	tree;
	vector<wstring>					keys;

	volatile bool appended;
	vector<wchar_t>	appended_characters;

	volatile bool removed;
	vector<wchar_t>	removed_characters;
};
